package com.bruce.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序
 * <br>CreateDate  2021/10/27 20:27:03
 *
 * @author luotuan
 * @version 1.0.0
 */
public class insertSort {
    public static void main(String[] args) {
        int[] array = {1,3,2,6,8,10,20,11,9};
        System.out.println(Arrays.toString(sort(array)));
    }
    public static int[] sort(int[] array){
        int len = array.length;
        if(len<=1){
            return array;
        }
        for(int i=1; i<len;i++){
            int value = array[i];
            int j = i-1;
            //找到插入的位置
            for(;j>=0;j--){
                if(value<array[j]){
                    // 移动
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            // 插入
            array[j+1] = value;
        }
        return array;
    }
}
